#include "graphsupporttest/TestFacilityLocationSolver.h"

#include <boost/shared_ptr.hpp>

#include "boosttestsupport.h"

#include "accumulsupport/AccumulSupport.h"

#include "graphsupport/graph/operation/CompoundGraphOperation.h"
#include "graphsupport/graph/operation/GenBipartLinkNear.h"
#include "graphsupport/graph/generate/DefaultGraphGenerator.h"
#include "graphsupport/graph/operation/AddChpExpWeightsOperation.h"
#include "graphsupport/graph/operation/MakeSymmOperation.h"
#include "graphsupport/graph/operation/GeneratePricesOperation.h"
#include "graphsupport/graph/operation/TriangleInequalityCloseOperation.h"

#include "graphsupport/solve/facilitylocation/BinaryRunFacilityLocationSolver.h"
#include "graphsupport/solve/facilitylocation/CompoundFacilitiesSolver.h"
#include "graphsupport/solve/facilitylocation/PrimalDualFacilitiesLocationSolver.h"
#include "graphsupport/solve/facilitylocation/ChooseCheapestFacilityHeuristic.h"
#include "graphsupport/solve/facilitylocation/RemoveUnusedFacilityHeuristic.h"
#include "graphsupport/solve/facilitylocation/RemoveUnusedFacilityHeuristic.h"

void solveTrivial(
	FacilitiesGraph & fgraph,
	std::vector< char > & isFacilityOpenVec,
	std::vector< int > & cityWitnessVec
)
{
	int n = fgraph.getVertexCount();
	Graph::AdjMatrixType adjMatr = fgraph.getAdjacentMatrixArr();

	for ( int i = 0; i < fgraph.getCitiesCount(); i++ )
	{
		Graph::AdjCoefType minEdg = fgraph.getInfEdge();
		int witness = -1;
		for ( int j = fgraph.getCitiesCount(); j < n; j++ )
		{
			if ( adjMatr[i][j] < minEdg )
			{
				minEdg = adjMatr[i][j];
				witness = j;
			}
		}
		isFacilityOpenVec[witness - fgraph.getCitiesCount()] = true;
		cityWitnessVec[i] = witness - fgraph.getCitiesCount();
	}
}

void TestFacilityLocationSolver()
{
	int vertCount = 20;
	int neighbors = 4;
	int firstBipart = vertCount / 2;
	int secondBipart = vertCount - firstBipart;
	Graph::AdjCoefType cheap = 100;
	Graph::AdjCoefType expensive = 200;

	CompoundGraphOperation * mainOp = new CompoundGraphOperation();
	IGraphOperationPtr mainOpPtr( mainOp );
	GenBipartLinkNear * bipartGen = new GenBipartLinkNear();
	mainOp->addSubOperation( IGraphOperationPtr( bipartGen ) );
	mainOp->addSubOperation( IGraphOperationPtr( new AddChpExpWeightsOperation() ) );
	mainOp->addSubOperation( IGraphOperationPtr( new MakeSymmOperation() ) );

	DefaultGraphGenerator defGenerator( mainOpPtr );

	FacilitiesGraph fgraph;
	IOperationSettings oset( firstBipart, secondBipart );
	oset.neighborsBeg = neighbors;
	oset.neighborsRange = 1;
	defGenerator.generateGraph( fgraph, oset );

	BOOST_CHECK_EQUAL( firstBipart, fgraph.getFirstBipart() );
	BOOST_CHECK_EQUAL( secondBipart, fgraph.getSecondBipart() );

	// ### ### ### ### ### ### ### ### ### ### ### ### ### ### ###

	Graph::AdjMatrixType adjMatr = fgraph.getAdjacentMatrixArr();

	BinaryRunFacilityLocationSolver brfSolver;
	IFacilityLocationSolver * solver = & brfSolver;

	std::vector< char > isFacilityOpenVec( secondBipart, 0 );
	std::vector< int > cityWitnessVec( firstBipart, -1 );
	accumf::reinit( fgraph.facilitiesPrices, fgraph.getFacilitiesCount(), 123 );
	bool solved = solver->solve( fgraph, isFacilityOpenVec, cityWitnessVec );
	BOOST_CHECK( solved );

	FacilitiesGraph::FacilityPriceType sumConnections = 0;
	for ( int i = 0; i < firstBipart; i++ )
	{
		int wintess = cityWitnessVec[i];
		BOOST_CHECK_GT( wintess, -1 );
		if ( wintess == -1 )
		{
			std::cout << " i = " << i << " wintess = " << wintess;
			break;
		}
		BOOST_CHECK( isFacilityOpenVec[wintess] );
		if ( !isFacilityOpenVec[wintess] )
		{
			std::cout << " i = " << i << " wintess = " << wintess <<
				" isFacilityOpenVec[wintess] = " << (bool)isFacilityOpenVec[wintess];
			break;
		}
		sumConnections += fgraph.getFSEdge( i, wintess );
	}

	FacilitiesGraph::FacilityPriceType sumFacilities = 0;
	for ( int i = 0; i < secondBipart; i++ )
	{
		if ( isFacilityOpenVec[i] )
		{
			sumFacilities += fgraph.facilitiesPrices[i];
		}
	}

	accumf::reinit( isFacilityOpenVec, secondBipart, 0 );
	accumf::reinit( cityWitnessVec, firstBipart, -1 );
	solveTrivial( fgraph, isFacilityOpenVec, cityWitnessVec );

	FacilitiesGraph::FacilityPriceType sumConnections1 = 0;
	for ( int i = 0; i < firstBipart; i++ )
	{
		int wintess = cityWitnessVec[i];
		BOOST_CHECK_GT( wintess, -1 );
		if ( wintess == -1 )
		{
			std::cout << " i = " << i << " wintess = " << wintess;
			break;
		}
		BOOST_CHECK( isFacilityOpenVec[wintess] );
		if ( !isFacilityOpenVec[wintess] )
		{
			std::cout << " i = " << i << " wintess = " << wintess <<
				" isFacilityOpenVec[wintess] = " << (bool)isFacilityOpenVec[wintess];
			break;
		}
		sumConnections1 += fgraph.getFSEdge( i, wintess );
	}

	FacilitiesGraph::FacilityPriceType sumFacilities1 = 0;
	for ( int i = 0; i < secondBipart; i++ )
	{
		if ( isFacilityOpenVec[i] )
		{
			sumFacilities1 += fgraph.facilitiesPrices[i];
		}
	}

	BOOST_CHECK_LT( sumConnections + sumFacilities, fgraph.getInfEdge() );
	BOOST_CHECK_LE( sumConnections + sumFacilities, sumConnections1 + sumFacilities1 );
}

void TestSolutionDoesnotExist()
{
	int vertCount = 20;
	int neighbors = 3;
	int firstBipart = vertCount / 2;
	int secondBipart = vertCount - firstBipart;

	CompoundGraphOperation * mainOp = new CompoundGraphOperation();
	IGraphOperationPtr mainOpPtr( mainOp );
	GenBipartLinkNear * bipartGen = new GenBipartLinkNear();
	mainOp->addSubOperation( IGraphOperationPtr( bipartGen ) );
	mainOp->addSubOperation( IGraphOperationPtr( new AddChpExpWeightsOperation() ) );
	mainOp->addSubOperation( IGraphOperationPtr( new MakeSymmOperation() ) );

	DefaultGraphGenerator defGenerator( mainOpPtr );

	FacilitiesGraph fgraph;
	IOperationSettings oset( firstBipart, secondBipart );
	oset.neighborsBeg = neighbors;
	oset.neighborsRange = 1;
	defGenerator.generateGraph( fgraph, oset );
	CRITICAL_CHECK( fgraph.getCitiesCount() == firstBipart );

	for ( int i = firstBipart; i < vertCount; i++ )
	{
		fgraph.eraseEdge( 0, i );
	}

	// ### ### ### ### ### ### ### ### ### ### ### ### ### ### ###

	Graph::AdjMatrixType adjMatr = fgraph.getAdjacentMatrixArr();
	FacilitiesGraph::FacilityPricesVecType facilitiesPriceVec( secondBipart, 123 );

	BinaryRunFacilityLocationSolver brfSolver;

	std::vector< char > isFacilityOpenVec( secondBipart, 0 );
	std::vector< int > cityWitnessVec( firstBipart, -1 );
	bool solved = brfSolver.solve( fgraph, isFacilityOpenVec, cityWitnessVec );
	BOOST_CHECK( !solved );
}

class PredefineSolutionData
{
public:
	PredefineSolutionData( int n, int firstBipart )
		: n( n )
		, firstBipart( firstBipart )
		, cheap( 50 )
		, cheapRange( 10 )
		, expensive( 200 )
		, expensiveRange( 90 )
		, expectedNeighbors( n / 10 )
		, neighborsRange( n / 15 )
		, expectedUsedFacilities( 3 )
		, expectedUsedFacilitiesRange( n - firstBipart - expectedUsedFacilities )
		, expectedPrice( 70 )
		, priceRange( 40 )
	{
	}

	/**
	 * Note: the constructor has too much arguments but it is test-only class
	 */
	PredefineSolutionData(
		int n,
		int firstBipart,
		int cheap,
		int cheapRange,
		int expensive,
		int expensiveRange,
		int expectedNeighbors,
		int neighborsRange,
		int expectedUsedFacilities,
		int expectedUsedFacilitiesRange,
		int expectedPrice,
		int priceRange,
		int runsCount
	)
		: n( n )
		, firstBipart( firstBipart )
		, cheap( cheap )
		, cheapRange( cheapRange )
		, expensive( expensive )
		, expensiveRange( expensiveRange )
		, expectedNeighbors( expectedNeighbors )
		, neighborsRange( neighborsRange )
		, expectedUsedFacilities( expectedUsedFacilities )
		, expectedUsedFacilitiesRange( expectedUsedFacilitiesRange )
		, expectedPrice( expectedPrice )
		, priceRange( priceRange )
		, runsCount( runsCount )
	{
	}

	std::string toString()
	{
		std::stringstream buf;
		buf << "n="						<< n
			<< " firstBipart="			<< firstBipart
			<< " cheap="				<< cheap
			<< " cheapRange="			<< cheapRange
			<< " expensive="			<< expensive
			<< " expensiveRange="		<< expensiveRange
			<< " expectedNeighbors="	<< expectedNeighbors
			<< " neighborsRange="		<< neighborsRange << "\n"
			<< "\texpectedPrice="		<< expectedPrice
			<< " priceRange="			<< priceRange;

		return buf.str();
	}

public:
	int n;
	int firstBipart;

	int cheap;
	int cheapRange;
	int expensive;
	int expensiveRange;
	int expectedNeighbors;
	int neighborsRange;
	int expectedUsedFacilities;
	int expectedUsedFacilitiesRange;
	int expectedPrice;
	int priceRange;

	int runsCount;
};

class PredefineSolution : public IGraphOperation, public IFacilityLocationSolver
{
public:
	PredefineSolution()
		: sampler( boost::mt19937( ( unsigned ) 12345 ), boost::uniform_int<>( 0, 1 << 30 ) )
		, data( 0, 0 ) // TODO: make cities facilities
	{
	}

	virtual void applyTo( Graph & graph, IOperationSettings & )
	{
		FacilitiesGraph * fgraph = dynamic_cast< FacilitiesGraph *  >( & graph );
		CRITICAL_CHECK( fgraph != 0 );

		fgraph->initBi( data.firstBipart, data.n - data.firstBipart );
		assert( graph.getVertexCount() > 0 );
		assert( graph.getVertexCount() == data.n );
		int secondBipart = data.n - data.firstBipart;
		graph.eraseAllEdges();
		Graph::AdjMatrixType adjMatr = graph.getAdjacentMatrixArr();

		accumf::reinit( isFacilityOpenVec, secondBipart, 0 );
		accumf::reinit( cityWitnessVec, data.firstBipart, -1 );
		facilitiesPriceVec.resize( secondBipart );

		std::vector< int > plannedToUseFacilities;
		int ptufSize = data.expectedUsedFacilities + sampler() % data.expectedUsedFacilitiesRange;
		for ( int i = 0; i < ptufSize; i++ )
		{
			int facility = sampler() % secondBipart + data.firstBipart;
			plannedToUseFacilities.push_back( facility );
		}

		for ( int i = 0; i < data.firstBipart; i++ )
		{
			int witnessPos = sampler() % plannedToUseFacilities.size();
			int witness = plannedToUseFacilities[witnessPos];
			cityWitnessVec[i] = witness - fgraph->getCitiesCount();
			adjMatr[i][witness] = data.cheap + sampler() % data.cheapRange;
			isFacilityOpenVec[witness - data.firstBipart] = true;
		}

		for ( int i = 0; i < data.n; i++ )
		{
			int neighCount = data.expectedNeighbors + sampler() % data.neighborsRange;
			for ( int j = 0; j < neighCount; j++ )
			{
				int neigh = sampler() % secondBipart + data.firstBipart;
				adjMatr[i][neigh] = data.expensive + sampler() % data.expensiveRange;
			}
		}

		for ( int i = 0; i < secondBipart; i++ )
		{
			facilitiesPriceVec[i] = data.expectedPrice + sampler() % data.priceRange;
		}

		MakeSymmOperation::makeSymm( graph );
		fgraph->facilitiesPrices = facilitiesPriceVec;
	}

	virtual bool solve(
		FacilitiesGraph & fgraph,
		std::vector< char > & isFacilityOpenVec,
		std::vector< int > & cityWitnessVec
	)
	{
		isFacilityOpenVec = this->isFacilityOpenVec;
		cityWitnessVec = this->cityWitnessVec;
	}

public:
	PredefineSolutionData data;

public:
	FacilitiesGraph::FacilityPricesVecType facilitiesPriceVec;

private:
	boost::variate_generator< boost::mt19937, boost::uniform_int<> > sampler;
	std::vector< char > isFacilityOpenVec;
	std::vector< int > cityWitnessVec;
};

void TestBinRunFoundAtLeastPredefined()
{
	if ( BoostTestEnv::getBinRunTestCount() > 5 )
	{
		std::cout << "\nTestBinRunFoundAtLeastPredefined cases: " <<BoostTestEnv::getBinRunTestCount();
	}

	std::stringstream sstream;

	int status = BoostTestEnv::getBinRunStatus();

	std::ostream & shortReport = status == BoostTestEnv::BIN_RUN_RAND_SHORT ? std::cout : sstream;
	std::ostream & detailReport = status == BoostTestEnv::BIN_RUN_RAND_DETAILED ? std::cout : sstream;

	FacilitiesGraph fgraph;

	PredefineSolutionData dataset[] = {
		PredefineSolutionData (
			50, // n
			37, // firstBipart
			30, // cheap
			10, // cheapRange
			300, // expensive
			30, // expensiveRange
			50 / 10, // expNeights
			50 / 15, //neightsRange
			3, //expectedUsedFacilities,
			10, //expectedUsedFacilitiesRange,
			270, // expectedPrice
			20, // priceRange
			BoostTestEnv::getBinRunTestCount() // runs count
		),
		PredefineSolutionData (
			50, // n
			37, // firstBipart
			50, // cheap
			30, // cheapRange
			100, // expensive
			100, // expensiveRange
			50 / 10, // expNeights
			50 / 15, //neightsRange
			3, //expectedUsedFacilities,
			10, //expectedUsedFacilitiesRange,
			270, // expectedPrice
			20, // priceRange
			BoostTestEnv::getBinRunTestCount() // runs count
		),
		PredefineSolutionData (
			50, // n
			37, // firstBipart
			30, // cheap
			10, // cheapRange
			300, // expensive
			30, // expensiveRange
			50 / 10, // expNeights
			50 / 15, //neightsRange
			3, //expectedUsedFacilities,
			10, //expectedUsedFacilitiesRange,
			100, // expectedPrice
			300, // priceRange
			BoostTestEnv::getBinRunTestCount() // runs count
		),
		PredefineSolutionData (
			50, // n
			37, // firstBipart
			50, // cheap
			300, // cheapRange
			200, // expensive
			200, // expensiveRange
			50 / 10, // expNeights
			50 / 15, //neightsRange
			3, //expectedUsedFacilities,
			10, //expectedUsedFacilitiesRange,
			300, // expectedPrice
			400, // priceRange
			BoostTestEnv::getBinRunTestCount() // runs count
		),
		PredefineSolutionData (
			512, // n
			500, // firstBipart
			30, // cheap
			30, // cheapRange
			100, // expensive
			30, // expensiveRange
			50 / 10, // expNeights
			50 / 15, //neightsRange
			3, //expectedUsedFacilities,
			10, //expectedUsedFacilitiesRange,
			270, // expectedPrice
			20, // priceRange
			BoostTestEnv::getBinRunTestCount() // runs count
		),
		PredefineSolutionData (
			30, // n
			16, // firstBipart
			30, // cheap
			30, // cheapRange
			100, // expensive
			30, // expensiveRange
			50 / 10, // expNeights
			50 / 15, //neightsRange
			3, //expectedUsedFacilities,
			10, //expectedUsedFacilitiesRange,
			270, // expectedPrice
			20, // priceRange
			BoostTestEnv::getBinRunTestCount() // runs count
		),
	};

	std::stringstream failBuf;
	int failsCount = 0;

	int testCaseCount = sizeof( dataset ) / sizeof( PredefineSolutionData );
	shortReport << "predef-binrun defferences: ";
	for ( int index = 0; index < testCaseCount; index++ )
	{
		shortReport << "[" << index << "]: ";
		PredefineSolution psol;

		PredefineSolutionData & data = dataset[index];
		psol.data = data;
		int secondBipart = data.n - data.firstBipart;

		detailReport << "test case: " << data.toString() << "\n";

		for ( int runCount = 0; runCount < data.runsCount; runCount++ )
		{
			psol.applyTo( fgraph, IOperationSettings::EMPTY_SETTINGS );

			std::vector< char > isOpen0( secondBipart );
			std::vector< int > cityWtn0( data.firstBipart );
			BinaryRunFacilityLocationSolver().solve(
				fgraph,
				isOpen0,
				cityWtn0
			);
			FacilitiesGraph::FacilityPriceType cost0 = IFacilityLocationSolver::computeCost(
				fgraph,
				isOpen0,
				cityWtn0
			);

			BOOST_CHECK_LT( cost0, fgraph.getInfEdge() );

			std::vector< char > isOpen1( secondBipart );
			std::vector< int > cityWtn1( data.firstBipart );
			psol.solve(
				fgraph,
				isOpen1,
				cityWtn1
			);
			FacilitiesGraph::FacilityPriceType cost1 = IFacilityLocationSolver::computeCost(
				fgraph,
				isOpen1,
				cityWtn1
			);

			BOOST_CHECK_LE( cost0, cost1 );
			detailReport << "\t\t[" << index << ", " << runCount << "]cost0: " << cost0 << " cost1: " << cost1 << " diff: " << ( cost1 - cost0 ) << "\n";
			shortReport << ( cost1 - cost0 ) << ", ";

			if ( cost0 > cost1 )
			{
				failBuf << "[" << index << ", " << runCount << "]fail: " << data.toString() << "\npredef facilities:\t";
				for ( int i = 0; i < secondBipart; i++ )
				{
					failBuf << "[" << i << "#" << i + data.firstBipart << ":" << (int)isOpen1[i] << "] ";
				}
				failBuf << "\n";
				for ( int i = 0; i < secondBipart; i++ )
				{
					failBuf << (int)isOpen1[i];
				}
				failBuf << "\nsolver facilities:\t";
				for ( int i = 0; i < secondBipart; i++ )
				{
					failBuf << "[" << i << "#" << i + data.firstBipart << ":" << (int)isOpen0[i] << "] ";
				}
				failsCount++;
			}
		}
	}

	if ( failsCount > 0 )
	{
		std::cout << "\n\n" << failBuf.str();
	}
}

class FakeRelinkSolver : public IFacilityLocationSolver
{
public:
	virtual bool solve(
		FacilitiesGraph & fgraph,
		std::vector< char > & isFacilityOpenVec,
		std::vector< int > & cityWitnessVec
	)
	{
		int facilitiesCount = fgraph.getFacilitiesCount();

		CRITICAL_CHECK( fgraph.getCitiesCount() == cityWitnessVec.size() );
		CRITICAL_CHECK( fgraph.getFacilitiesCount() == isFacilityOpenVec.size() );

		for ( int city = 0; city < fgraph.getCitiesCount(); city++ )
		{
			int witness = cityWitnessVec[city];
			for ( int facility = 0; facility < fgraph.getFacilitiesCount(); facility++ )
			{
				if ( fgraph.existsBiPartEdge( city, facility ) )
				{
					if ( fgraph.getFSEdge( city, witness ) > fgraph.getFSEdge( city, facility ) )
					{
						cityWitnessVec[city] = facility;
						return true;
					}
				}
			}
		}

		return true;
	}
};

class FakeAddExceedFacilitySolver : public IFacilityLocationSolver
{
public:
	virtual bool solve(
		FacilitiesGraph & fgraph,
		std::vector< char > & isFacilityOpenVec,
		std::vector< int > & cityWitnessVec
	)
	{
		int facilitiesCount = fgraph.getFacilitiesCount();

		CRITICAL_CHECK( fgraph.getCitiesCount() == cityWitnessVec.size() );
		CRITICAL_CHECK( fgraph.getFacilitiesCount() == isFacilityOpenVec.size() );

		for ( int facility = 0; facility < facilitiesCount; facility++ )
		{
			if ( !isFacilityOpenVec[facility] )
			{
				isFacilityOpenVec[facility] = true;
				break;
			}
		}

		return true;
	}
};

void TestCompoundSolver()
{
//	IGNORE( "TestCompoundSolver" );
	FacilitiesGraph fgraph;

	int citiesCount = 300;
	int facilitiesCount = 100;

	IGraphGeneratorPtr graphGenerator(
		new DefaultGraphGenerator(
			CompoundGraphOperation::createOperation(
				5,
				new GenBipartLinkNear(),
				new AddChpExpWeightsOperation(),
				new MakeSymmOperation(),
				new GeneratePricesOperation(),
				new TriangleInequalityCloseOperation()
			)
		)
	);

	IOperationSettings oset( citiesCount, facilitiesCount );
	oset.neighborsBeg = 5;
	oset.neighborsRange = 10;
	graphGenerator->generateGraph( fgraph, oset );
	CRITICAL_CHECK( fgraph.getCitiesCount() == citiesCount );

	CompoundFacilitiesSolver compoundSolver;
	compoundSolver.addSubSolver( IFacilityLocationSolverPtr(
		new PrimalDualFacilitiesLocationSolver()
	) );
	compoundSolver.addSubSolver( IFacilityLocationSolverPtr(
		new FakeRelinkSolver()
	) );

	std::vector< char > isFacilityOpenVec;
	std::vector< int > cityWitnessVec;
	bool solved = compoundSolver.solve(
		fgraph,
		isFacilityOpenVec,
		cityWitnessVec
	);
	BOOST_CHECK( solved );
	CRITICAL_CHECK( isFacilityOpenVec.size() == fgraph.getFacilitiesCount() );
	CRITICAL_CHECK( cityWitnessVec.size() == fgraph.getCitiesCount() );
	FacilitiesGraph::FacilityPriceType priceA =
		IFacilityLocationSolver::computeCost(
			fgraph,
			isFacilityOpenVec,
			cityWitnessVec
		);

	compoundSolver.addSubSolver( IFacilityLocationSolverPtr(
		new ChooseCheapestFacilityHeuristic()
	) );
	compoundSolver.addSubSolver( IFacilityLocationSolverPtr(
		new FakeAddExceedFacilitySolver()
	) );

	solved = compoundSolver.solve(
		fgraph,
		isFacilityOpenVec,
		cityWitnessVec
	);
	BOOST_CHECK( solved );
	FacilitiesGraph::FacilityPriceType priceB =
		IFacilityLocationSolver::computeCost(
			fgraph,
			isFacilityOpenVec,
			cityWitnessVec
		);
	BOOST_CHECK_GT( priceA, priceB );

	compoundSolver.addSubSolver( IFacilityLocationSolverPtr(
		new RemoveUnusedFacilityHeuristic()
	) );
	solved = compoundSolver.solve(
		fgraph,
		isFacilityOpenVec,
		cityWitnessVec
	);
	BOOST_CHECK( solved );
	FacilitiesGraph::FacilityPriceType priceC =
		IFacilityLocationSolver::computeCost(
			fgraph,
			isFacilityOpenVec,
			cityWitnessVec
		);
	BOOST_CHECK_LT( priceC, priceB );
}
